package LeetCode1;

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * 前K个高频元素
 * 取大用小,JDK优先队列默认是小堆
 *
 * @author 是阿秋啊
 * @date 2022/03/16 15:11
 **/
public class Num347 {
    //先创建一个自定义类存储不重复元素以及出现次数，并实现比较器
    private class Freq implements Comparable<Freq> {
        private int key;
        private int times;

        public Freq(int key, int times) {
            this.key = key;
            this.times = times;
        }

        @Override
        public int compareTo(Freq o) {
            return this.times - o.times;
        }
    }

    public int[] topKFrequent(int[] nums, int k) {
        int[] ret = new int[k];
        Map<Integer, Integer> map = new HashMap<>();
        //1.遍历数组，统计在map集合中
        for (int i : nums) {
            //map.put(i,map.getOrDefault(i,0) + 1);
            //下边操作等同于上边注释
            if (map.containsKey(i)) {
                //次数i已经存储过，出现次数 + 1
                map.put(i, map.get(i) + 1);
            } else {
                //第一次出现
                map.put(i, 1);
            }
        }
        //2.扫描map集合，将前k个出现次数最高的的元素放入优先队列
        Queue<Freq> queue = new PriorityQueue<>();
        for (Map.Entry<Integer,Integer> entry : map.entrySet()) {
            if (queue.size() < k) {
                queue.offer(new Freq(entry.getKey(),entry.getValue()));
            } else {
                //判断堆顶元素出现次数与当前元素出现次数大小
                Freq freq = queue.peek();
                if (entry.getValue() > freq.times) {
                    queue.poll();
                    queue.offer(new Freq(entry.getKey(),entry.getValue()));
                }
            }
        }
        //3.此时优先队列中存储的元素，为题目要求的k个元素
        for (int i = 0; i < k; i++) {
            ret[i] = queue.poll().key;
        }
        return ret;
    }
}
